\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{itemize}
\item
  修改 \(x\) 位置的值为 \(y\)
\item
  查询区间 \([l,r]\)是否可以重排为值域上连续的一段
\end{itemize}

维护序列 \(2^{a_1},2^{a_2},...,2^{a_n}\) 的和\\
若 \(a_x,a_{x+1},...a_u\) 重排后若在值域上连续，则
\(\sum_{i=x}^y2^i=\sum_{i=Min}^{Max}2^i=2^{Max+1}-2^{Min}\)

\begin{lstlisting}
#define ull unsigned long long
#define ll long long 
#define int long long
using namespace std;
const ll INF (0x3f3f3f3f3f3f3f3fll);
const int N = 5e5 + 10;
const int M = 5e5 + 10;
int a[M] , n , m;
ull power[N] , base = 233 , tot[N];
ull pow_mod(ll x , ll n){ull res = 1 ; while(n) {if(n & 1) res = res * x ; x = x * x ; n >>= 1 ;} return res;}
struct Seg_Tree{
	int l , r , mi;
	ull sum;
}tree[M << 2]; 
void push_up(int rt)
{
	tree[rt].mi = min(tree[rt << 1].mi , tree[rt << 1 | 1].mi);
	tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
}
void build(int l , int r , int rt , int *aa)
{
	tree[rt].l = l , tree[rt].r = r;
	if(l == r)
	{
		tree[rt].mi = aa[l];
		tree[rt].sum = pow_mod(base , aa[l]);
		return ;
	}
	int mid = l + r >> 1;
	build(l , mid , rt << 1 , aa);
	build(mid + 1 , r , rt << 1 | 1 , aa);
	push_up(rt);
}
void update(int pos , int val , int rt)
{
	int l = tree[rt].l , r = tree[rt].r;
	if(l == r) 
	{
		tree[rt].mi = val;
		tree[rt].sum = pow_mod(base , val);
		return ;
	}
	int mid = l + r >> 1;
	if(pos <= mid) update(pos , val , rt << 1);
	else if(pos > mid) update(pos , val , rt << 1 | 1);
	push_up(rt);
}
int query_min(int L , int R , int rt)
{
	int l = tree[rt].l , r = tree[rt].r;
	if(L <= l && r <= R) return tree[rt].mi ;
	int mid = l + r >> 1 , res = INF;
	if(L <= mid) res = min(res , query_min(L , R , rt << 1));
	if(R > mid) res = min(res , query_min(L , R , rt << 1 | 1));
	return res;
}
ull query_sum(int L , int R , int rt)
{
	int l = tree[rt].l , r = tree[rt].r;
	if(L <= l && r <= R) return tree[rt].sum;
	int mid = l + r >> 1;
	ull res = 0;
	if(L <= mid) res += query_sum(L , R , rt << 1);
	if(R > mid) res += query_sum(L , R , rt << 1 | 1);
	return res;
}
const ull mod = 19260817337;
void init()
{
	power[0] = 1 , tot[0] = 1;
	for(int i = 1 ; i <= N - 10 ; i ++) power[i] = power[i - 1] * base , tot[i] = tot[i - 1] + power[i];
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0); 
	init();
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	build(1 , n , 1 , a);
	while(m --)
	{
		int op;
		cin >> op;
		if(op == 1) 
		{
			int pos , val;
			cin >> pos >> val;
			update(pos , val , 1);
		}
		else
		{
			int l , r;
			cin >> l >> r;
			int mi = query_min(l , r , 1);
			ull sum = query_sum(l , r , 1);
			ull ad = pow_mod(base , mi - 1);
			if(sum == ad * (tot[r - l + 1] - 1)) cout << "damushen\n";
			else cout << "yuanxing\n";
		}
	}
	return 0;
}
\end{lstlisting}

\end{document}
